package com.cong.leetcode._164;

class Solution {
    int [] nums;
    int res = 0;
    public int maximumGap(int[] nums) {
        if (nums.length < 2)
            return 0;
        this.nums = nums;
        return 0;
    }
    public int[] sort(int start, int end) {
        assert start <= end;
        if (start == end)
            return new int[]{nums[start]};

        int mid = (start + end) / 2; // 相当于floor
        int[] numsI = sort(start, mid);
        int[] numsJ = sort(mid + 1, end);
        int[] r = new int[end - start + 1];
        for (int i = start, j = mid + 1, p = 0; p < r.length; p ++) {
            if (j > end || j < i)
                j = i;
            if (i > mid)
                i = j;
            int diff = numsJ[j] - numsI[i];
            if (diff < 0) {
                r[p] = nums[j];
                res = Math.max((-diff), res);
                j++;
            }else {
                r[p] = nums[i];
                i++;
                res = Math.max(diff, res);
            }
        }

        return r;
    }
}